package com.algorithms.leetcode.Arrays;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 注意：答案中不可以包含重复的三元组。
 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/3sum
 * <br>
 */
public class leetcode_15_threeSum {
    /**
     * https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> allList = new ArrayList<>();
        if(nums == null || nums.length < 3){
            return allList ;
        }
        //排序
        Arrays.sort(nums);
        for(int i = 0;i < nums.length;i++){
            if(nums[i] > 0){
                break;
            }
            //此处必须是 nums[i] == nums[i - 1]
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int l = i + 1;
            int r = nums.length - 1;
            while (l < r){
                int sum = nums[i] + nums[l] + nums[r];
                if(sum == 0){
                    allList.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    while (l<r && nums[l] == nums[l+1]) {
                        l++; // 去重
                    }
                    while (l<r && nums[r] == nums[r-1]) {
                        r--; // 去重
                    }
                    l++;
                    r--;
                }
                if(sum < 0){
                    //右移一位
                    l++;
                }

                if(sum > 0){
                    r--;
                }
            }
        }
        return allList;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(threeSum(new int[]{-1,0,1,2,-1,-4}).toArray()));
    }
}


